#include <cstdlib>
#define ElemType int
#define InitSize 100

typedef struct //动态分配容量的顺序表
{
    ElemType *data; //存储空间基址(首地址)
    int length;     //顺序表当前长度
    int Maxsize;    //顺序表最大容量
} SeqList;

//手动扩容顺序表
void IncreaseSize(SeqList &L, int len)
{
    int *p = L.data;
    L.data = (ElemType *)malloc((L.Maxsize + len) * sizeof(ElemType));
    for (int i = 0; i < L.length; i++) //将原来的数据复制回来
        L.data[i] = p[i];
    L.Maxsize = L.Maxsize + len;
    free(p); //释放数组p的内存。这步其实可以省略，因为在IncreaseSize()函数的生命周期结束后会自动释放申请的内存
    return;
}

//插入 O(n)
bool ListInsert(SeqList &L, int i, ElemType e) //在位序为i 的位置插入一个数e
{
    if (i < 1 || i > L.length + 1) //判断i 的范围是否有效(1 <= i <= L.length+1 )
        return false;
    if (L.length >= L.Maxsize) //判断当前存储空间是否已满，若已满则不可插入
        return false;
    for (int j = L.length; j >= i; j--) //将位序为i 的元素及之后的元素后移一位
        L.data[j] = L.data[j - 1];
    L.data[i - 1] = e; //在位序i 放入e
    L.length++;        //顺序表长度加1
    return true;
}

//删除 O(n)
bool ListDelete(SeqList &L, int i, ElemType &e) //删除顺序表中第i 个位置的元素，并用e 带回
{
    if (i < 1 || i > L.length) //判断i 的范围是否有效(1 <= i <= L.length)
        return false;
    e = L.data[i - 1];                 //即将被删除的元素被赋值给e
    for (int j = i; j < L.length; j++) //将第i 个位置后面的元素前移
        L.data[j - 1] = L.data[j];
    L.length--; //顺序表长度减1
    return true;
}

//按值查找 O(n)
int LocateElem(SeqList L, ElemType e) //查找顺序表中第一个元素值等于e 的元素，并返回其位序
{
    for (int i = 0; i < L.length; i++)
        if (L.data[i] == e)
            return i + 1; //下标为i 的元素等于e，返回其位序i+1
    return 0;             //查找失败，返回0
}